﻿#region Header

/*
Behavioral Rating of Dancing Human Crowds based on Motion Patterns
By

Pascal Hauser 
Dipl. Ing. in Informatik, Hochschule für Technik Rapperswil, 2006
Master Thesis, Hochschule für Technik Rapperswil, 2008-2010

and

Raphael Gfeller
Dipl. Ing. in Informatik, Hochschule für Technik Rapperswil, 2006
Master Thesis, Hochschule für Technik Rapperswil, 2008-2010

*/

#endregion

#region Usings

using System.Collections.Generic;
using System.Linq;
using Sebarf.Services.Interfaces;

#endregion

namespace paravili.Services {
	/// <summary>
	/// Does the matching by 
	/// 1. Apply the Trim algorithm.
	///   http://de.wikipedia.org/wiki/Algorithmus_von_Prim
	/// while (node has more than two outgoing connection)
	///		Eliminate unnecessary connection by remoting the connection with the highest value 
	/// </summary>
	public class DoMatchingByPrimAlgorithmService : Service, IDoMatchingService {
		#region Private Methods

		private static IList<Match> eliminateunnecessaryConnection(IList<Match> shortestConnection, int[,] originalData) {
			bool found;
			do {
				found = false;
				Dictionary<int, IList<KeyValuePair<int, double>>> incoming = calculateIngoungConnection(shortestConnection,
																										 originalData);
				foreach (var i in incoming) {
					if (i.Value.Count > 1) {
						KeyValuePair<int, double> highestCost = i.Value.OrderBy(x => x.Value).First();
						Match toRemove = shortestConnection.First(x => x.ToIndex == i.Key && x.FromIndex == highestCost.Key);
						shortestConnection.Remove(toRemove);
						found = true;
					}
				}
			} while (found);

			return shortestConnection;
		}

		private static List<Match> calculateShortestTree(IDictionary<int, IList<KeyValuePair<int, double>>> connection,
														  int[,] data) {
			var includeList = new List<int>();
			for (int i = 0; i < data.GetLength(0); i++) {
				includeList.Add(i);
			}
			var toReturn = new List<Match>();
			Match nextMatch;
			do {
				nextMatch = findShortestMatch(connection, includeList);
				if (nextMatch != null) {
					toReturn.Add(nextMatch);
				}
			} while (nextMatch != null);
			return toReturn;
		}

		private static Match findShortestMatch(IDictionary<int, IList<KeyValuePair<int, double>>> connection,
												ICollection<int> includeList) {
			if (includeList.Count == 0) {
				return null;
			}
			double shortestMatch = double.MinValue;
			int from = -1;
			int to = -1;
			foreach (int source in includeList) {
				if (connection.ContainsKey(source)) {
					foreach (var cnn in connection[source]) {
						if (includeList.Contains(cnn.Key)) {
							if (cnn.Value > shortestMatch) {
								from = source;
								to = cnn.Key;
								shortestMatch = cnn.Value;
							}
						}
					}
				}
			}
			includeList.Remove(from);
			if (from < 0 || shortestMatch < int.MinValue) {
				return null;
			}

			return new Match { FromIndex = from, ToIndex = to, Distance = shortestMatch };
		}

		private static int[,] eliminateAtoADistances(int[,] data) {
			for (int i = 0; i < data.GetLength(0); i++) {
				data[i, i] = int.MinValue;
			}
			return data;
		}

		private static int[,] eliminateTwoFaceConnection(int[,] data) {
			for (int i = 0; i < data.GetLength(0); i++) {
				for (int y = 0; y < data.GetLength(1); y++) {
					if (data[i, y] > int.MinValue && data[y, i] > int.MinValue) {
						if (i == y) {
							continue;
						}
						if (data[i, y] > data[y, i]) {
							data[y, i] = int.MinValue;
						}
						else {
							data[i, y] = int.MinValue;
						}
					}
				}
			}
			return data;
		}

		private static Dictionary<int, IList<KeyValuePair<int, double>>> calculateOutgoingConnection(int[,] data) {
			var toReturn = new Dictionary<int, IList<KeyValuePair<int, double>>>();
			for (int i = 0; i < data.GetLength(0); i++) {
				var outConnections = new List<KeyValuePair<int, double>>();
				for (int y = 0; y < data.GetLength(0); y++) {
					if (data[i, y] > int.MinValue) {
						outConnections.Add(new KeyValuePair<int, double>(y, data[i, y]));
					}
				}
				if (outConnections.Count > 0) {
					toReturn.Add(i, outConnections);
				}
			}
			return toReturn;
		}

		private static Dictionary<int, IList<KeyValuePair<int, double>>> calculateIngoungConnection(IEnumerable<Match> data,
																									 int[,] originalData) {
			var toReturn = new Dictionary<int, IList<KeyValuePair<int, double>>>();
			foreach (Match match in data) {
				IList<KeyValuePair<int, double>> inConnections = new List<KeyValuePair<int, double>>();

				if (toReturn.ContainsKey(match.ToIndex)) {
					inConnections = toReturn[match.ToIndex];
				}
				else {
					toReturn.Add(match.ToIndex, inConnections);
				}
				inConnections.Add(new KeyValuePair<int, double>(match.FromIndex, originalData[match.FromIndex, match.ToIndex]));
			}
			return toReturn;
		}

		#endregion

		#region IDoMatchingService Members

		public Match[] FindMatch(int[,] data) {
			// eliminate two way connection
			data = eliminateTwoFaceConnection(data);
			// eliminate a to a connection
			data = eliminateAtoADistances(data);

			// calculates outgoing connections
			Dictionary<int, IList<KeyValuePair<int, double>>> outConnection = calculateOutgoingConnection(data);

			//calculate shortes tree
			List<Match> shortetsConnection = calculateShortestTree(outConnection, data);

			IList<Match> reducedConnection = eliminateunnecessaryConnection(shortetsConnection, data);

			return reducedConnection.ToArray();
		}

		#endregion
	}
}